package com.company.ljh.medium;
/**
 * 给定一个 完美二叉树 ，其所有叶子节点都在同一层，每个父节点都有两个子节点。
 * 填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。
 *
 * 初始状态下，所有 next 指针都被设置为 NULL。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/populating-next-right-pointers-in-each-node
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
 * @description:
 * @projectName:leet_code
 * @see:com.company.ljh.medium
 * @author:ljh
 * @createTime:2022/5/31 10:33
 * @version:1.0
 */
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
public class 填充每个节点的下一个右侧节点指针 {
    /**
     * 1.广度优先遍历，将两个结点的左子结点与右子结点连接，左结点的右结点与右结点的左子结点，右结点的左子结点与右子结点连接
     * @param root
     * @return
     */
    public Node connect(Node root) {
        if(root != null){
            doConnect(root.left,root.right);
        }
        return root;
    }
    private void doConnect(Node root1,Node root2){
        if(root1 == null && root2==null){
            return;
        }else{
            root1.next = root2;
            doConnect(root1.left,root1.right);
            doConnect(root1.right,root2.left);
            doConnect(root2.left,root2.right);
        }
    }
    /**
     * 2.使用已建立的 \text{next}next 指针
     * 通过父结点已经和父结点的右结点建立指针，因此可以拿到父结点的右结点的左子结点
     */

}
